//https://codeforces.com/problemset/problem/1734/C
//贪心
//注意控制时间复杂度（注意memset函数）
#include<bits/stdc++.h>
using namespace std;
int cost[1000005]={0};
char s[1000005];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            cost[i]=0;
        }
        cin>>s;
        for(int i=1;i<=n;i++){
            if(s[i-1]=='0'){
                for(int j=i;j<=n;j+=i){
                    if(s[j-1]=='1') break;
                    if(cost[j]==0){
                        cost[j]=i;
                    }
                }
            }
        }
        long long ans=0;        
        for(int i=1;i<=n;i++){
            ans+=cost[i];
        }
        printf("%lld\n",ans);
    }
}